All-resistant pokemon types

It turns out you can! Whether through trial and error or a search method like best-first search, or (as I'll describe later) using math tools such as integer linear programming, you can solve this problem and find a type combination that resists everything. Here's one example:

[water, water, poison, poison, ground, dark, flying, steel]

Together, this list of eight types has 1/2x weakness or less to every single attacking type. You can use the Pokemon type chart to check each attacking type. (It is also the "smallest" example of an all-resistant type combination: it uses eight types in its list, and no other resistant type combination can be made with eight or fewer types.)

I was pretty pleased with this result. It's a short, elegant list of types, and it is resistant to any attack you throw at it. The rock-paper-scissors interactions between the types can be solved for a beautiful self-supporting structure. But still, I felt curious…

I had found my one all-resistant type combination. I wondered if there were any others besides the one I found.

There were a few ways to build more all-resistant types, I realized, because if you have an all-resistant list of types, you can combine it with itself to make a list that's twice as long, and the result will be 1/4x resistant to everything instead of just 1/2x. And if I ever found two genuinely different all-resistant type combinations, I could combine them together, too, to make a larger all-resistant type.

And, if you reason about it carefully, if you have any two all-resistant combinations and combine them together, you can add one more of any type (like one more electric, or one more fire, or one more ghost, or…) and the result will still be resitant to everything²

So I had three recipes for building new all-resistant type combinations out of the ones I had. In schematic form, if R and S are all-resistant type combinations and T is a single type such as electric, fire, or ghost, then:

1. R+R will still be all-resistant.
2. R+S will still be all-resistant.
3. R+S+T will still be all-resistant.

But the problem with these examples is that they're boring. They're not really showing you new ways to build all-resistant types, because they're built out of type combinations we've already got. I wanted to know if there were any genuinely new ways to build all-resistant type combinations, besides the one that I found.

I was looking for all the genuinely unique ways of building all-resistant types. "Genuinely unique" meant that it wasn't just a mashup of some smaller all-resistant types. There are a few choices for what "genuinely unique" actually means; I decided on the rule:

Rule: An all-resistant type combination is genuinely unique if it doesn't have any smaller all-resistant type combinations inside of it. Or, to put it another way, when you're assembling it out of individual types one by one, there's no way to make an all-resistant combination using just some of the pieces. It only becomes all-resistant when the final piece is added.

Those are the type combinations I wanted to find. Each one is a unique way of making all-resistance that I had never seen before. They're the building blocks—the periodic table—of all-resistant type combinations; once you've found all of them, you can combine them together in infinite combinations to make all the rest.

This was my quest: to find and list every unique all-resistant type combination.

Normally we combine type effectivenesses by multiplying: water is 2x weak to electric, and flying is 2x weak to electric, so [water, flying] is 4x weak to electric.

"Taking logarithms" means that the type effectivenesses (2x, 1x, 1/2x, and 0x) become what I call "susceptibilities": (+1, 0, -1, and -∞). By making this substitution in the type chart, you can combine by adding instead of multiplying. Flying has +1 susceptibility to electric, and water has +1 susceptibility to electric, so [flying,water] has +2 susceptibility. Or, ground is susceptible to water (+1) but grass is resistant to water (-1), so [ground, grass] is neutral to water (0). Finally, immunity becomes -∞: it is negative (so resistant), and no types you add to it can change that.

Adding is much more convenient than multiplying, especially when you're dealing with long lists of types. It also makes it possible to compute type-resistance using matrix multiplication, which computers can do very efficiently.

If you take the type chart and replace all of the effectivenesses with their corresponding susceptibilities, you get an 18x18 susceptibility matrix \(S\).

A type combination like [water, ground] is a size-18 vector with a 1 in the water index, a 1 in the ground index, and zeroes elsewhere. In general, you can represent a type combination as a size-18 vector where each row is one of the types, and the value in that row is the amount of that type you have³.

When you do this, you can compute the resistance of any type combination x by doing matrix multiplication \[S\cdot x\]. The result is a vector listing your susceptibility to each type.

And the problem we're trying to solve is: find all of the type combinations that resist everything, i.e. find all the type combinations x where (a) \(S\cdot x \leq -1\); this is the mathematical way to say that x has susceptibility -1 or less to every attack, i.e. x resists every attack. (b) x is a valid type combination, meaning the entries of x have to be integers (amounts of each type), and they can't be negative amounts. (you can't have "negative amounts of water" in a type combination)

It turns out that there are special computer programs designed to solve problem of this type; if you want to read more about it, this is known as "integer linear programming".

Susceptibilities make our lives easier in many ways, because we can add susceptibilities instead of multiplying effectivenesses, and because they make the problem "linear" so there are lots of tools for solving it effectively.

But they do introduce one problem, namely with immunities. In terms of susceptibilities, immunity is represented by -∞. Infinities are a huge problem—they break the tools that are designed to handle linear problems, because they are singularities that break the linear structure.

Here's the trick I invented to bypass this problem. We're searching a vast landscape of type combinations, and have a lot of choices: do we include flying, if so how much? do we include normal, if so how much?

It's convenient to start by dividing up the search based on types that grant immunity. After all, if you know in advance that you're searching type combinations that contain steel (which is immune to poison), you can relax and not worry about keeping track of how much poison weakness you're tacking on — the steel will neutralize all of it.

There are seven types that grant immunity:

1. flying is immune to ground
2. normal is immune to ghost
3. ghost is immune to normal
4. dark is immune to psychic
5. ground is immune to electric
6. steel is immune to poison
7. fairy is immune to dragon

So, each of these gives you a way to split your search region in half: on one side are all the types that contain steel (for example), and on the other side are types that contain no steel. On the one side, your type combination will have poison immunity no matter what else you add onto it.

And my clever insight is that both of these regions give you a way to simplify the type chart:

1. If you decide in advance that you're considering only steel-containing type combinations, then poison attacks never have an effect on anything. You can zero out the poison-attack row in the type chart so that poison attacks are now neutral against everything^{4, 5} Notice that this change to the type chart won't change the answers you find — anything that's all-resistant under the new type chart and contains steel will be all-resistant under the old type chart. And notice that by zeroing out this row, we've eliminated an infinity from the table.
2. If you decide in advance that you're considering only steel-excluding type combinations, then steels defenses will never matter. (It doesn't matter what steel is resistant or weak to, because we've decided not to use steel as an ingredient). We can zero out that column of the type chart. When we do, notice that we've eliminated an infinity from the table.

So we have seven immunity-granting types. Each one divides the search space into two regions. Within each region, we can mutate the type chart to make it simpler, eliminating the immunities/infinities that were caused by that type. In theory, this is 2⁷=128 regions, each with their own mutated type chart. And each of those 128 mutated type charts has no infinities in it. We can therefore use our ordinary linear programming tools without worrying that they will break.

I mentioned that in theory there are 2⁷=128 regions, if you're allowed to choose immunity-granting types independently of one another. But in fact, in our current, specific type chart, there are some immunities you're forced to include if you want an all-resistant type combination:

1. If you want to resist all types, you must resist dragon. But dragon is only resisted by fairy or steel. Therefore, you must contain fairy or steel or both — you can't leave them both out.
2. If you want to resist all types, you must resist ghost. But ghost is only resisted by normal or dark. Therefore, you must contain normal or dark or both — you can't leave them both out.
3. If you want to resist all types, you must resist ground and flying simultaneously. But in the type chart, everything that resists ground is weak to flying, and vice versa. The only type that resolves the stalemate is flying, therefore you must include flying in every all-resistant type.

By weird coincidence⁶, each of these requirements forces you to introduce immunity-granting types.

Instead of seven independent binary choices resulting in 128 different regions, we instead have a reduced selection of choices:

{flying} x {normal, dark, both} x {fairy, steel, both} x {ground, no ground} x {ghost, no ghost}

That's 1x3x3x2x2 = 36 regions instead of 128, and so 36 regions with their own mutated type charts to consider.

I call these thirty-six regions cones for technical mathematical reasons — the space of solutions to "find all all-resistant type combinations in this region" is shaped like a "linear cone". (This is because you can multiply an all-resistant type combination by any positive amount and the result will still be all-resistant. So, visually speaking, you get "rays" of all-resistant types extending out to infinity, which makes it "cone-shaped".)

I found the original minimal eight-type combination using best-first search. Then, with the help of a friend, I realized I could take logarithms and use integer linear programming tools to compute the answer instantly.

I spent the next few years diving into the linear structure. I learned about the term "linear cones" and "integer lattice points on polyhedra" and "homogenization of polyhedra to produce cones"; I learned that the type combinations I was looking for were the "pareto frontier" of the all-resistant solutions (because they represent the leanest ways of producing all-resistant types, such that the tradeoffs are all maximally efficient.) I learned about Dickson's lemma, a mathematical result which proved that there had to be a finite number of minimal all-resistant types — though whether that meant dozens or quadrillions, I never was able to prove. I learned about hilbert bases for cones and proved that the pareto frontier was a subset — usually thousands of times smaller subset — of the hilbert basis. I was introduced to the program normaliz, and spent years of parallel compute time to find the hilbert bases of my thirty-six cone regions with their mutated charts. This turned out to be a bust, in the end: while it's technically true that the hilbert basis contains the pareto frontier, it is so expensive to compute the hilbert basis that it's not worth it. Some of the cones had fairly quick hilbert basis calculations — finishing in a few seconds or minutes or hours. Others took weeks. These were useful, at least, for providing independent confirmation. But eventually I found that one of the cones, I estimated, would've taken four hundred years to complete using all the considerable computational resources I could throw at it. Throughout this project, I often wondered whether I would find the solution in my lifetime. It was time to go back to the drawing board.

Eventually, I went back to search, the method I started with. I had written several branch-and-bound programs over the years, but they had all failed in mysterious ways — I don't recall exactly what had gone on, but as I recall, the general principle of "use an ILP as an oracle to decide if there's a solution in this space and return the minimal one, then use branch and bound to divide up the space until you've found all the minimal ones" was failing due to numerical errors in the ILP library. This persisted even when I tried writing in several different languages or using different solver libraries.

When I finally returned to search, those numerical problems were gone. But it was still taking forever to search. I still needed one final trick. Here was the algorithm I was using at the time:

1. Initialize a list of proven minimal all-resistant types, initially empty.
2. The search agenda consists of rectangular regions of pokemon type-combinations to search. Rectangular means that you can put lower limits and upper limits on each of the types, for example "Don't use more than two electric", or "Use at least one steel", or "Don't use any dark", or "Use between one and three water".
3. Initially, the agenda contains the thirty-six regions.
4. Until the agenda is empty, pop off one of the rectangular regions.
5. Ask the integer linear program if this region has an all-resistant type in it, and if it does, to return the smallest one.
6. Compare that smallest one to the list of candidate all-resistant types. If none of the candidates beat it (i.e. are leaner — use strictly fewer types), then add it to the list. [As I recall: Otherwise, skip it and iterate on the loop.]
7. Use that smallest type combo to break the current rectangular region into a bunch of new subregions regions to check. The new regions to check are the ones that use less of some type — less normal, or less fire, or less water, or … etc. Put those new subregions into the agenda and go back to the beginning of the loop.

The first part of the trick is memoization: this method will tend to produce the same subregions over and over, so when you pop a region off the agenda, check whether you've seen it before, and if you have, skip it.

The second part of the trick is what I call lexicographic boxes. When we split into subregions, we're trying to search a venn diagram of "uses less normal or less fire or less water or … ". If we do the naive thing and search each of the types independently (search through all types that use less normal, then all types that use less fire, then …), we'll be covering a lot of the same regions over and over, wasting a ton of work.

The solution is to search each segment of the venn diagram once, by being more clever about how we divide up the rectangle. We have a list of types in order: normal, fire, water, grass, … . What we do is impose an invariant: instead of searching "all types that use less water", we're going to search "all types that use less water (but not less normal or fire, the types that come before water in the list)". In other words, we search regions that use less of each type, but not less of any of the types that come before it in the list.

If we impose this condition, we end up covering the area — we cover the entire venn diagram — but each of the regions we search are disjoint from the rest so we never repeat ourselves. That saves us so much work, it transforms a search problem that might take millenia to finish into one that finishes in a few minutes.

That's the main intellectual innovation here. I also use parallelization to explore candidates in parallel, but that's a technical cherry on top.